#ifndef _BFS_HH_
#define _BFS_HH_
#include "State.h"
#include "Torus.hh"
#include <queue>
#include <utility>
#include <set>

///
/// Breadth first Search generic template
///
/// Calls __action for each __valid_position in BFS order
///
struct bfs_node
{
    uLocation cell;
    int direction; // last direction used to come to current cell
    unsigned depth;

    bfs_node(uLocation _loc, int _direction, unsigned _depth) :
        cell(_loc), direction(_direction), depth(_depth)
    { }
};

template<typename _Action, typename _Condition>
void breadth_first_search(Map & map, uLocation sLoc, _Action & __action, _Condition & __valid_position)
{
    std::set<uLocation> visited;
    std::queue<bfs_node> locQueue;
    locQueue.push(bfs_node(sLoc, -1, 0));

    visited.insert(sLoc);

    while(!locQueue.empty())
    {
        bfs_node node = locQueue.front();
        locQueue.pop();
        uLocation cLoc = node.cell;
        unsigned depth = node.depth;

        if(!__action(map,node)) return;

        for(int d=0; d<Map::TDIRECTIONS; d++)
	{
	    uLocation nLoc = map.getLocation(cLoc, d);
            if(!visited.count(nLoc) && __valid_position(map,sLoc,nLoc,depth))
	    {
                locQueue.push(bfs_node(nLoc, d, depth+1));
	    }
            visited.insert(nLoc);
	}
    }
}

/// Functor for direct walking potentials
/// i.e. do not avoid dangerous positions
struct valid_for_walking_t
{
    unsigned distance;

    valid_for_walking_t(unsigned _distance) : distance(_distance) {}

    bool operator()(Map & map, uLocation sLoc, uLocation nLoc, unsigned depth)
    {
        return (!map[nLoc].isWater)&&(depth < distance);
    }
};


/// Functor for safe walking potentials
/// i.e. avoid dangerous positions
struct valid_for_safe_walking_t
{
    unsigned distance;

    valid_for_safe_walking_t(unsigned _distance) : distance(_distance) {}

    bool operator()(Map & map, uLocation sLoc, uLocation nLoc, unsigned depth)
    {
        return (!map[nLoc].isWater)&& map[nLoc].isSafe && (depth < distance);
    }
};


///
/// Walking BFS template
///
template<typename _Action>
void walk( Map & map, uLocation sLoc, unsigned distance, _Action & __action)
{
    valid_for_walking_t valid2walk(distance);
    breadth_first_search(map, sLoc, __action, valid2walk);
}


///
/// Safe Walking BFS template
///
template<typename _Action>
void safe_walk( Map & map, uLocation sLoc, unsigned distance, _Action & __action)
{
    valid_for_safe_walking_t valid4safe_walk(distance);
    breadth_first_search(map, sLoc, __action, valid4safe_walk);
}



#endif /* _BFS_HH_ */
